import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessBoard {
    public static int X = 6;//col
    public static int Y = 6;//row
//    public static int step = 1;
    public static int[][] chessBoard = new int[Y][X];
    public static boolean[] is_visited = new boolean[X * Y];
    public static boolean finished = false;

    public static void travelHorse(int[][] chessboard,int row,int col,int step){
        is_visited[row * X + col] = true;
        chessboard[row][col] = step;
        ArrayList<Point> points = nextPoint(new Point(col, row));//x,y默认从0开始
        sort(points);
        while(!points.isEmpty()){
            Point p = points.removeFirst();
            if(!is_visited[p.y * X + p.x]){
                travelHorse(chessboard,p.y,p.x,step + 1);
            }
        }
        if(step < X * Y && !finished){
            is_visited[row * X + col] = false;
            chessboard[row][col] = 0;
        }else{
            finished = true;
        }

    }

    public static ArrayList<Point> nextPoint(Point p){
        ArrayList<Point> ps = new ArrayList<>();
        Point point = new Point();
        if((point.x = p.x + 2) < X && (point.y = p.y - 1) >= 0 ){
            ps.add(new Point(point));
        }
        if((point.x = p.x + 2) < X && (point.y = p.y + 1) < Y ){
            ps.add(new Point(point));
        }
        if((point.x = p.x + 1) < X && (point.y = p.y - 2) >= 0){
            ps.add(new Point(point));
        }
        if((point.x = p.x + 1) < X && (point.y = p.y + 2) < Y){
            ps.add(new Point(point));
        }
        if((point.x = p.x - 2) >= 0 && (point.y = p.y - 1) >= 0){
            ps.add(new Point(point));
        }
        if((point.x = p.x - 2) >= 0 && (point.y = p.y + 1) < Y ){
            ps.add(new Point(point));
        }
        if((point.x = p.x - 1) >= 0 && (point.y = p.y + 2) < Y){
            ps.add(new Point(point));
        }
        if((point.x = p.x - 1) >= 0 && (point.y = p.y - 2) >= 0 ){
            ps.add(new Point(point));
        }
        return ps;
    }
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return nextPoint(o1).size() - nextPoint(o2).size();
            }
        });
    }
    public static void main(String[] args) {
//        HorseChessBoard horseChessBoard = new HorseChessBoard();
        int row = 3;
        int col = 4;
        long start = System.currentTimeMillis();
        travelHorse(chessBoard,row -1 ,col - 1,1);
        long end = System.currentTimeMillis();
        System.out.println("time is " + (end - start));
        for (int[] ints : chessBoard) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }

    }
}





